package mine.personal.demo.pratice.algorithm.bitcaculation;

/**
 * @Author: lhl
 * @CreateTime: 2025-04-07
 * @Description: 位运算算法合集
 * @Version: 1.0
 */
public class Solution {
    /**
     * leetcode -> 判断字符是否唯一(引入额外数据结构的解法)
     * @author: 李鸿麟
     * @date: 2025/4/7
     * @param: astr
     * @return: boolean
     */
    public boolean isUnique(String astr) {
        char[] s = astr.toCharArray();
        int[] hash = new int[26];
        for (int i = 0; i < s.length; i++) {
            hash[s[i] - 'a']++;
        }
        for (int x : hash) {
            if (x >= 2) {
                return false;
            }
        }
        return true;
    }

    /**
     * leetcode -> 判断字符是否唯一(不引入额外数据结构的解法 -- 位图思想)
     * @author: 李鸿麟
     * @date: 2025/4/7
     * @param: astr
     * @return: boolean
     */
    public boolean isUnique2(String astr) {
        // 鸽巢原理做一个优化 英文字母一共只有26个 所以一串没有重复字母的最长字符串的长度只可能是26 但凡长度>26 就代表一定有重复的字母
        if (astr.length() > 26) {
            return false;
        }
        int bitMap = 0;
        for (int i = 0; i < astr.length(); i++) {
            int x = astr.charAt(i) - 'a';
            // 判断是否重复
            if (((bitMap >> x) & 1) == 1) {
                return false;
            }
            // 不重复 则把当前字母加入位图
            bitMap |= 1 << x;
        }
        return true;
    }

    /**
     * leetcode -> 丢失的数字(位运算解法)
     * @author: 李鸿麟
     * @date: 2025/4/7
     * @param: nums
     * @return: int
     */
    public int missingNumber(int[] nums) {
        int a = 0;
        for (int i = 0; i < nums.length; i++) {
            a ^= nums[i];
        }
        for (int i = 0; i <= nums.length; i++) {
            a ^= i;
        }
        return a;
    }

    /**
     * leetcode -> 丢失的数字(高斯求和解法)
     * @author: 李鸿麟
     * @date: 2025/4/7
     * @param: nums
     * @return: int
     */
    public int missingNumber2(int[] nums) {
        int n = nums.length;
        int sum1 = n*(n+1)/2;
        int sum2 = 0;
        for (int i = 0; i < n; i++) {
            sum2 += nums[i];
        }
        return sum1 - sum2;
    }

    /**
     * leetcode -> 不使用加法运算符的加法实现
     * @author: 李鸿麟
     * @date: 2025/4/8
     * @param: a
     * @param: b
     * @return: int
     */
    public int getSum(int a, int b) {
        while (b != 0) {
            int x = a ^ b;
            int carry = (a & b) << 1;
            a = x;
            b = carry;
        }
        return a;
    }

    /**
     * leetcode -> 只出现了一次的数字
     * @author: 李鸿麟
     * @date: 2025/4/9
     * @param: nums
     * @return: int
     */
    public int singleNumber(int[] nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int x : nums) {
                if (((x >> i) & 1) == 1) {
                    sum++;
                }
            }
            sum %= 3;
            if (sum == 1) {
                ret |= 1 << i;
            }
        }
        return ret;
    }

    /**
     * leetcode -> 丢失的两个数字
     * @author: 李鸿麟
     * @date: 2025/4/14
     * @param: nums
     * @return: int
     */
    public int[] missingTwo(int[] nums) {
        int n = nums.length;
        int tmp = 0;

        // 第一次两组数异或 可以得到缺失的两个数字的异或结果
        for (int i = 0; i < n; i++) {
            tmp ^= nums[i];
        }
        for (int i = 1; i <= n + 2; i++) {
            tmp ^= i;
        }

        // 为了出现两个缺失的数字 需要再找一个可以区分这两个数字的标准 即第一位不相同的比特位
        int x = 0;
        while(true){
            if (((tmp >> x) & 1) == 1) {
                break;
            } else {
                x++;
            }
        }
        int[] ret = new int[2];

        // 第二次两组数异或 可以得到缺失的两个数字
        for (int p : nums) {
            if (((p >> x) & 1) == 1) {
                ret[0] ^= p;
            } else {
                ret[1] ^= p;
            }
        }
        for (int i = 1; i <= n + 2; i++) {
            if (((i >> x) & 1) == 1) {
                ret[0] ^= i;
            } else {
                ret[1] ^= i;
            }
        }
        return ret;
    }
}
